/*
  This file is part of streaminfo.

    Foobar is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.

    Foobar is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with Foobar.  If not, see <http://www.gnu.org/licenses/>.
*/

#include <string>
#include <map>
#include <iostream>

#include "stream_summary.h"

template<class T>
heavy_hitters<T>::heavy_hitters(int max_counters)  :
  stream_summary(NULL),
  summary_size(0),
  MAX_COUNTERS(max_counters)
{
}

template<class T>
class bucket {
  friend class heavy_hitters<T>;
protected:
  int value;
  counter<T>* list;
  bucket<T>* next;
  bucket<T>* prev;
};

template<class T>
class counter {
  friend class heavy_hitters<T>;
protected:
  T *value;
  bucket<T> *parent;
  int error;
  counter<T> *next;
  counter<T> *prev;
};

template<class T>
void
heavy_hitters<T>::heavy_hitters_replace_min(T *token)
{
  typename std::unordered_map<T,counter<T>*>::iterator iter;
  if(summary_size < 1)
    return;

  bucket<T> *min_bucket = stream_summary;
  counter<T> *min_counter = min_bucket->list;
  int new_value = min_bucket->value + 1;

  //Update min counter to point to the new token.
  min_counter->error = min_bucket->value;
  min_bucket->list = min_counter->next;
  if(min_bucket->list)
    min_bucket->list->prev = NULL;
  if (min_bucket->next && min_bucket->next->value == new_value) {
    //insert in next bucket over
    bucket<T> *new_bucket = min_bucket->next;
    min_counter->next = new_bucket->list;
    if(min_counter->next)
      min_counter->next->prev = min_counter;
    min_counter->parent = new_bucket;
    new_bucket->list = min_counter;
  } else {
    //make a new next bucket
    bucket<T> *new_bucket = new bucket<T>();
    new_bucket->next = min_bucket->next;
    if(new_bucket->next)
      new_bucket->next->prev = new_bucket;
    new_bucket->prev = min_bucket;
    min_bucket->next = new_bucket;
    new_bucket->value = new_value;
    min_counter->parent = new_bucket;
    min_counter->next = NULL;
    new_bucket->list = min_counter;
  }

  if (min_bucket->list == NULL) {
    stream_summary = min_bucket->next;
    stream_summary->prev = NULL;
    delete min_bucket;
  }

  //now replace in the map.
  iter = counters.find(*min_counter->value);
  counters.erase(iter);
  counters.insert( std::make_pair( *token, min_counter ));
  delete min_counter->value;
  min_counter->value = token;
}

template<class T>
void 
heavy_hitters<T>::heavy_hitters_add (tokentype &token)
{
  typename std::unordered_map<tokentype,counter<T>*>::iterator iter = counters.find(token);
  if (iter != counters.end()) {
    counter<T> *cur_counter = iter->second;
    bucket<T> *cur_bucket = cur_counter->parent;
    bucket<T> *next_bucket = cur_bucket->next;
    if(cur_bucket->next && cur_bucket->value + 1 == cur_bucket->next->value) {
      //just move current counter to the next list
    } else {
      //create a new bucket, and then move cur_counter to the next list
      next_bucket = new bucket<T>();
      next_bucket->value = cur_bucket->value + 1;
      next_bucket->prev = cur_bucket;
      next_bucket->next = cur_bucket->next;
      cur_bucket->next = next_bucket;
      if(next_bucket->next)
	next_bucket->next->prev = next_bucket;
    }
    //move the new counter
    if(cur_bucket->list == cur_counter)
      cur_bucket->list = cur_counter->next;
    if(cur_counter->prev)
      cur_counter->prev->next = cur_counter->next;
    if(cur_counter->next)
      cur_counter->next->prev = cur_counter->prev;
    cur_counter->prev = NULL;
    cur_counter->next = next_bucket->list;
    if(cur_counter->next)
      cur_counter->next->prev = cur_counter;
    cur_counter->parent = next_bucket;
    next_bucket->list = cur_counter;
    //check if we need to change the head
    if (cur_bucket->list == NULL) {
      if(cur_bucket->prev)
	cur_bucket->prev->next = cur_bucket->next;
      cur_bucket->next->prev = cur_bucket->prev;
      if(stream_summary == cur_bucket)
	stream_summary = cur_bucket->next;
      delete cur_bucket;
    }
  } else {
    //need to make a copy of the token to make it permanent
    tokentype *token_copy = new tokentype(token);
    
    if(summary_size < MAX_COUNTERS) {
      ++summary_size;
      counter<T> *new_counter = new counter<T>();
      if(!stream_summary || stream_summary->value != 1) {
	//create a new 0 bucket
	bucket<T> *new_bucket = new bucket<T>();
	if(stream_summary)
	  new_bucket->next = stream_summary;
	else
	  new_bucket->next = NULL;
	stream_summary = new_bucket;
	new_bucket->value = 1;
	new_bucket->prev = NULL;
      } 
      //now add the new counter to stream_summary
      counters.insert( std::make_pair( *token_copy, new_counter) );
      new_counter->value = token_copy;
      new_counter->error = 0;
      new_counter->next = stream_summary->list;
      if(new_counter->next)
	new_counter->next->prev = new_counter;
      new_counter->prev = NULL;
      stream_summary->list = new_counter;
      new_counter->parent = stream_summary;
    } else {
      heavy_hitters_replace_min(token_copy);
    }
  }
}

template<class T>
void
heavy_hitters<T>::print_buckets()
{
  bucket<T>* cur_bucket = stream_summary;
  while(cur_bucket) {
    std::cout << "Bucket: " << cur_bucket->value << std::endl;
    counter<T>* cur_counter = cur_bucket->list;
    while(cur_counter) {
      std::cout << "counter: " << *cur_counter->value << " error: " <<
	cur_counter->error << std::endl;
      cur_counter = cur_counter->next;
    }
    cur_bucket = cur_bucket->next;
  }
}

template<class T>
void
heavy_hitters<T>::print_counters()
{
  for(typename std::unordered_map<tokentype,counter<T>*>::iterator iter = counters.begin();
      iter != counters.end(); iter++) {
    std::cout << iter->first << ": " << iter->second->parent->value <<
      " (error: " << iter->second->error << ")" << std::endl;
  }
}

template<class T>
void
heavy_hitters<T>::clear_counters()
{
  for(typename std::unordered_map<tokentype,counter<T>*>::iterator iter = counters.begin();
      iter != counters.end(); iter++){
    delete iter->second->value;
    delete iter->second;
  }
  bucket<T> *cur_bucket = stream_summary;
  while(cur_bucket) {
    bucket<T> *del_bucket = cur_bucket;
    cur_bucket = cur_bucket->next;
    delete del_bucket;
  }
}

template class heavy_hitters<int>;
template class heavy_hitters<std::string>;
